Bargaining networks model social or economic situations in which agents seekto form the most lucrative partnership with another agent from among severalalternatives. There has been a flurry of recent research studying Nashbargaining solutions (also called 'balanced outcomes') in bargaining networks,so that we now know when such solutions exist, and also that they can becomputed efficiently, even by market agents behaving in a natural manner. Inthis work we study a generalization of Nash bargaining, that models thepossibility of unequal 'bargaining powers'. This generalization was introducedin [KB+10], where it was shown that the corresponding 'unequal division' (UD)solutions exist if and only if Nash bargaining solutions exist, and also that acertain local dynamics converges to UD solutions when they exist. However, thebound on convergence time obtained for that dynamics was exponential in networksize for the unequal division case. This bound is tight, in the sense thatthere exists instances on which the dynamics of [KB+10] converges only afterexponential time. Other approaches, such as the one of Kleinberg and Tardos, donot generalize to the unsymmetrical case. Thus, the question of computationaltractability of UD solutions has remained open. In this paper, we provide anFPTAS for the computation of UD solutions, when such solutions exist. On agraph G=(V,E) with weights (i.e. pairwise profit opportunities) uniformlybounded above by 1, our FPTAS finds an \eps-UD solution in timepoly(|V|,1/\eps). We also provide a fast local algorithm for finding \eps-UDsolution, providing further justification that a market can find such asolution.
展开▼
